1. Field of the Invention
The present invention relates to a computer system, and deals more particularly with a method, system, and computer program product for improving the operation of real-time systems through optimizations in the scheduling of tasks.
2. Description of the Related Art
The tasks executed in real-time systems tend to be highly predictable in terms of their execution characteristics (which are also known as “release characteristics”). In particular the execution patterns of tasks in real-time systems that are based upon a task model referred to as the “periodic task model” are predictable in terms of two values, their period and their cost. The period of a task is an interval of time that represents the natural frequency of execution for the task. The cost for a task is also an interval of time, and represents the maximum time it takes the task to complete its required work in a single period. For example one task may execute once every five days, but only execute for 2 minutes within this five-day period; the period for this task is therefore 5 days while its cost is 2 minutes. Another task in the same system may execute once in every 10-millisecond interval, and have a cost of 10 microseconds. In the general case, each period (except the first) begins immediately at the end of the previous period. The semantically correct execution pattern is that an instance of a task becomes ready to run at the beginning of every period and must complete its work sometime before the end of the period in which it is invoked. The end of the period for a task invocation is called the deadline.
For a set of periodic tasks following the above model, it is easy to compute whether every invocation of every task will all meet their deadlines. The equation             ∑              I        =        1            N        ⁢                   ⁢                  C        I                    T        I              ≤      N    ⁢          (                        2                      1            /            N                          -        1            )      may be used to make this determination (referred to hereinafter as a feasibility determination), where C(I) is the execution cost of task I and T(I) is the period of task I (where uniform time units over all I=1 . . . N are used) and where priority among tasks is assigned according to the well-known rate-monotonic priority assignment (“RMA”) algorithm. (Briefly stated, tasks with shorter periods get higher priorities when using the RMA approach). Techniques for evaluating the feasibility of systems in this manner to determine whether all deadlines will be met are known in the art.
In most real-time systems, however, there are additional entities that may execute, in addition to the expected (schedulable) tasks, but which cannot be accounted for in the scheduling process or in the feasibility determination process just described. These entities are referred to herein as “non-schedulable entities” (“NSEs”). NSEs require computation time, and are generally necessary for operation of a typical system. An example of an NSE is a hardware interrupt event. In general, there is no way to predict when (or whether) a hardware interrupt or other similar NSEs will occur. NSEs are therefore typically invisible to feasibility and scheduling algorithms.
However, the computation time required when an NSE does execute may cause tasks to miss their deadlines, even though those tasks are dispatched according to a schedule shown to be feasible by the feasibility algorithm. The reason for this is that the system may execute some NSEs (such as hardware interrupts) in preference to the scheduled tasks. Since the NSEs are invisible to the feasibility algorithm, the scheduling process will tend to incorrectly assign the execution time of any NSEs that execute during the execution of a scheduled task to that scheduled task. For example, if the cost of a particular task is 20 arbitrary time units (ATUs), the system will expect that task to be finished after executing for 20 ATUs. If the task is not finished at that time, which will be the case if NSEs have executed during the 20 ATUs, the system will typically generate an error condition and the task will fail.
It should be noted that there are a few real-time systems that can distinguish between the execution of an NSE and the execution of a scheduled task. Examples include Real-time Mach and Linux/RT. However, these systems typically do not include NSEs in the feasibility algorithm. (For various theoretical reasons, ignoring NSEs in the feasibility computations is a reasonable approach: in many cases, NSEs may account for a very small fraction of the overall execution time, and thus the feasibility of the system is not adversely affected by NSEs. However, this requires that the NSEs are known to be independent from one another, and therefore do not have a cumulative effect. This assumption does not always hold. When NSEs disable interrupts, for example, the dispatcher or scheduler may not be able to access the processor sufficiently often to ensure that the system is not affected.)
As will be obvious, when a task exceeds its expected execution time due to occurrence of an NSE and is thus cancelled, serious inefficiencies result. It would be preferable to avoid cancelling tasks, increasing the likelihood that the task will run to completion, as long as the feasibility of the overall system could be ensured.
U.S. Pat. No. 5,640,563, titled “Multi-Media Computer Operating System and Method”, teaches a technique for scheduling tasks in real-time systems according to their deadlines (i.e. their required end times), rather than their start times, in order to reduce the processor overhead generated by the task scheduling operation. However, this patent does not teach a technique that accounts for execution in the presence of NSEs.
U.S. Pat. No. 5,408,663, titled “Computer-Implemented Method of Scheduling Tasks Constituting Project”, teaches a technique for optimizing project scheduling where the overall effects of task duration (including the total duration of the project or the project's cost) are unsatisfactory. Resources to be assigned to the tasks for the project are iteratively adjusted to see if the project duration can be shortened. This patent also does not teach a technique that accounts for execution in the presence of NSEs, and in particular, does not teach a technique for allowing tasks to continue executing for longer time intervals.
Accordingly, what is needed is an improved technique for scheduling tasks that avoids the problems of the prior art.